package algorithm
{
	
	import datastructure.Edge;
	
	import mx.controls.Alert;
	
	/**
	 * 
	 * @author juxuan
	 * 
	 */
	public class Mincost_Maxflow
	{
		/**
		 * 参数值之考虑天数N在7< N < 30的范围 
		 */				
		private const size:int = 60;	//顶点数	1102  size = 2(N + 1)
		private const INF:int = int.MAX_VALUE;
		
		private var edges:Array = new Array(size * 7);	//size * 40  14N
		private var index:Array = new Array(size);
		private var edgesNum:int = 0;
		private var pre:Array = new Array(size);
		
		private var source:int;	//源点
		private var sink:int;	//汇点
		private var dis:Array = new Array(size);
		private var queue:Array = new Array(size * 5);	//队列size * 10)
		
		private var vst:Array = new Array(size);
		
		
		/* 用户可输入变量*/
		private var daysNumber:int = 3;
		private var newNapkinPrice:int = 10;  
		private var fastWashDays:int = 2;
		private var slowWashDays:int = 3;
		private var fastWashCost:int = 3;
		private var slowWashCost:int = 2;
		
		/* 临时用变量*/
		private var require:Array = new Array(5,6,7);	//每天的餐巾需求量
		
		
		
		public function Mincost_Maxflow()
		{
			
		}
		
		/**
		 * 创建边 
		 * @param from
		 * @param to
		 * @param vol
		 * @param cost
		 * 
		 */		
		public function createEdge(from:int,to:int,vol:int,cost:int):void
		{
			var edge:Edge = new Edge();
			edge.from = from;
			edge.to = to;
			edge.vol = vol;
			edge.cost = cost;
			edge.next = this.index[from];

			trace("from:" + from + ";to:" + to + ";vol:" + vol + ";cost:" + cost + ";next:" + edge.next);
			this.edges[this.edgesNum] = edge;
			this.index[from] = this.edgesNum ++;
		}
		
		/**
		 * 添加边 
		 * @param from
		 * @param to
		 * @param vol
		 * @param cost
		 * 
		 */		
		public function addEdge(from:int,to:int,vol:int,cost:int):void
		{
			this.createEdge(from,to,vol,cost);
			this.createEdge(to,from,0,-cost);
		}
		
		
		
		
		private function memset(s:Array,value:int):void
		{
			for(var i:int = 0; i < s.length; i++)
			{
				s[i] = value;
			}
		}
		
		/**
		 * 构建问题的模型
		 * 
		 */		
		public function init():void
		{
			this.memset(this.index,-1);
			
			var N:int = this.daysNumber;
			var p:int = this.newNapkinPrice;
			var m:int = this.fastWashDays;
			var f:int = this.fastWashCost;
			var n:int = this.slowWashDays;
			var s:int = this.slowWashCost;
			
			this.source = 0;
			this.sink = N * 2 + 1;
			
			for(var i:int = 1; i <= N; i++)
			{
				var r:int = this.require[i-1];	//每天需要的餐巾数量
				this.addEdge(source,i,r,0);
				this.addEdge(source,i+N,INF,p);
				this.addEdge(i+N,sink,r,0);
				if(i+1 <= N)
				{
					this.addEdge(i,i+1,INF,0);
				}
				if(i+m <= N)
				{
					this.addEdge(i,i+N+m,INF,f);
				}
				if(i+n <= N)
				{
					this.addEdge(i,i+N+n,INF,s);
				}
			}
		}
		
		
		public function initParameter(dn:int,p:int,m:int,f:int,n:int,s:int,r:Array):void
		{
			this.daysNumber = dn;
			this.newNapkinPrice = p;
			this.fastWashDays = m;
			this.fastWashCost = f;
			this.slowWashDays = n;
			this.slowWashCost = s;
			this.require =r;
		}
		
		
		/**
		 * Shortest Path Faster Algorithm：求单源最短路径算法 
		 * @return 
		 * 
		 */		
		public function SPFA():Boolean
		{
			for(var j:int=0;j < size; j++)
			{
				this.dis[j] = this.INF;
			}
			this.memset(this.vst,0);
			this.memset(this.pre,-1);
			
			this.vst[this.source] = 1;
			this.dis[this.source] = 0;
			
			var l:int = 0;
			var r:int = 0;
			this.queue[r++] = this.source;
			
			while(l < r)
			{
				var now:int = this.queue[l++];
				this.vst[now] = 0;
				for(var i:int = this.index[now];i != -1;i = (this.edges[i] as Edge).next)
				{
					var e:Edge = this.edges[i] as Edge;
					var adj:int = e.to;
					if(e.vol > 0 && ((e.cost + this.dis[now]) < this.dis[adj]))
					{
						this.dis[adj] = this.dis[now] + e.cost;
						this.pre[adj] = i;
						if(!this.vst[adj])
						{
							this.vst[adj] = 1;
							this.queue[r++] = adj;
						}
					}
				}
			}
			
			if(this.dis[this.sink] == this.INF)
				return false;
			
			return true;
		}
		
		
		/**
		 * 最小费用最大流算法 
		 * @return 
		 * 
		 */		
		public function mcmf():int
		{
			var flow:int = 0;
			var cost:int = 0;
			
			while(this.SPFA())
			{	
				var minn:int = this.INF;
				var u:int;
				var i:int;
				u = this.sink;
				while(u != this.source)
				{
					minn = Math.min(minn,this.edges[this.pre[u]].vol);
					//trace(this.pre[u]);
					u = this.edges[this.pre[u]].from;
					
				}
				u = this.sink;
				while(u != this.source)
				{
					this.edges[this.pre[u]].vol -= minn;	//前向边
					this.edges[this.pre[u] ^ 1].vol += minn;	//后向边
					u = this.edges[this.pre[u]].from;
				}
				
				flow += minn;
				cost += this.dis[this.sink] * minn;
			}
			trace("最大流是：" + flow);	//最大流即为n天总共用完的餐巾数
			
			return cost;
		}
		
		
		
		/**
		 * 运行最小费用最大流算法 
		 * 
		 */		
		public function runMincost_Maxflow():int
		{
			
			//this.initIndex();
			//this.init();
		
			var ff:int = this.mcmf();
			trace("最小费用是" + ff);
			
			for(var i:int = 0; i < this.edgesNum;i++)
			{
				if(i % 2 == 1)
				{
					trace("边:" + this.edges[i].from + "" + this.edges[i].to + " vol is:" + this.edges[i].vol + "; cost is: " + this.edges[i].cost);
					
				}
				
			}
			
			trace("边数量：" + this.edgesNum )
			return ff;	
		}
		
		
		public function getEdges():Array
		{
			return this.edges;
		}
		
		public function getEdgesNum():int
		{
			return this.edgesNum;
		}
		
		/**
		 * 获取 第i天新买的餐巾数
		 * 
		 */		
		public function getNewBuyNapkin(newBuyNapkins:Array):void
		{
			trace("************第i天新买的餐巾数************");
			var now:int = this.source;
			
			for(var i:int = this.index[now];i != -1;i = (this.edges[i] as Edge).next)
			{
				var e:Edge = this.edges[i ^ 1] as Edge;
				if(e.from > this.daysNumber)
				{
					trace("第" + (e.from - this.daysNumber) + "天新买的餐巾数为：" + e.vol);
					newBuyNapkins[e.from - this.daysNumber - 1] = e.vol;
				}
				
			}
		}//	end getNewBuyNapkin
		
		/**
		 * 获取 第i天送慢洗和快洗的餐巾数
		 * 
		 */		
		public function getFastAndSlowWash(fastWashNapkins:Array,slowWashNapkins:Array):void
		{
			trace("************第i天送慢洗和快洗的餐巾数************");
			for(var d:int=1; d <= this.daysNumber; d++)
			{
				var now:int = d;
				
				for(var i:int = this.index[now];i != -1;i = (this.edges[i] as Edge).next)
				{
					var e:Edge = this.edges[i ^ 1] as Edge;
					if(e.from > this.daysNumber)	//送快洗和慢洗的
					{
						if(Math.abs(e.cost) == this.fastWashCost)
						{
							trace("第" + (e.from - this.daysNumber - this.fastWashDays) + "天送快洗的餐巾数为：" + e.vol);
							fastWashNapkins[e.from - this.daysNumber - this.fastWashDays - 1] = e.vol;
						}
						else
						{
							trace("第" + (e.from - this.daysNumber - this.slowWashDays) + "天送慢洗的餐巾数为：" + e.vol);
							slowWashNapkins[e.from - this.daysNumber - this.slowWashDays - 1] = e.vol;
						}
						
					}
				}
			}
		}// end getFastAndSlowWash
		
		/**
		 * 获取第i天延期洗的餐巾数 
		 * 
		 */		
		public function getDelayWash(delayWashNapkins:Array):void
		{
			trace("************第i天延期洗的餐巾数************");
			for(var d:int=1; d <= this.daysNumber; d++)
			{
				var now:int = d;
				for(var i:int = this.index[now];i != -1;i = (this.edges[i] as Edge).next)
				{
					var e:Edge = this.edges[i ^ 1] as Edge;
					if(e.from <= this.daysNumber && e.from != 0 && e.from > e.to)	
					{
						trace("第" + e.to + "天延期洗的餐巾数为：" + e.vol);
						delayWashNapkins[e.to - 1] = e.vol;
					}
				}
			}
		} // end getDelayWash
			
		
		
	}
}